# 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
# 
#  进阶： 
# 
#  
#  你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：head = [4,2,1,3]
# 输出：[1,2,3,4]
#  
# 
#  示例 2： 
# 
#  
# 输入：head = [-1,5,3,4,0]
# 输出：[-1,0,3,4,5]
#  
# 
#  示例 3： 
# 
#  
# 输入：head = []
# 输出：[]
#  
# 
#  
# 
#  提示： 
# 
#  
#  链表中节点的数目在范围 [0, 5 * 104] 内 
#  -105 <= Node.val <= 105 
#  
#  Related Topics 链表 双指针 分治 排序 归并排序 
#  👍 1324 👎 0


from typing import List, Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        dummy = ListNode(0, head)
        n = self.len_list(head)
        sub_len = 1
        while sub_len < n:
            prev, curr = dummy, dummy.next
            while curr:
                head1 = curr
                for _ in range(1, sub_len):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                head2 = curr.next
                curr.next = None
                curr = head2
                for _ in range(1, sub_len):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                next_sub = None
                if curr:
                    next_sub = curr.next
                    curr.next = None
                merge = self.merge(head1, head2)
                prev.next = merge
                while prev.next:
                    prev = prev.next
                curr = next_sub
            sub_len = sub_len * 2
        return dummy.next

    # 求链表长度
    def len_list(self, head: ListNode) -> int:
        n = 0
        node = head
        while node:
            n += 1
            node = node.next
        return n

    # 合并链表
    def merge(self, h1: ListNode, h2: ListNode) -> ListNode:
        if h1 is None:
            return h2
        if h2 is None:
            return h1
        if h1.val < h2.val:
            h1.next = self.merge(h1.next, h2)
            return h1
        else:
            h2.next = self.merge(h1, h2.next)
            return h2


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


def link_to_list(h: ListNode) -> List[int]:
    r = []
    node = h
    while node:
        r.append(node.val)
        node = node.next
    return r


# 归并排序
# 不断扩大步长, 合并有序链表
"""
循环链表: 最后一个节点进入循环处理: while a
停在最后一个节点, 不处理: while a.next
"""
# def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
#     if head is None:
#         return None
#     length = self.len_list(head)
#     # 归并排序
#     dummy = ListNode(0, head)
#     sub_length = 1
#     while sub_length < length:
#         prev, curr = dummy, dummy.next
#         while curr:
#             head1 = curr
#             # 先取sub_length 一段
#             for _ in range(1, sub_length):
#                 if curr.next:
#                     curr = curr.next
#                 else:
#                     break
#             # 再向后取sub_length 一段
#             head2 = curr.next
#             # 断开前 sub_length 段
#             curr.next = None
#             curr = head2
#             for _ in range(1, sub_length):
#                 if curr and curr.next:
#                     curr = curr.next
#                 else:
#                     break
#             next_sub = None
#             # 还有后续节点, 记录节点并断开
#             if curr:
#                 next_sub = curr.next
#                 curr.next = None
#
#             # 合并两段
#             merge = self.merge(head1, head2)
#             # 链接, 并移动到未处理的节点
#             prev.next = merge
#             while prev.next:
#                 prev = prev.next
#             curr = next_sub
#         sub_length = sub_length * 2
#     return dummy.next

if __name__ == '__main__':
    s = Solution()
    # head = [-1,5,3,4,0]
    h1 = ListNode(-1, ListNode(5, ListNode(3, ListNode(4, ListNode(0)))))
    s.sortList(h1)
    r1 = link_to_list(h1)
    e1 = [-1, 0, 3, 4, 5]
    assert r1 == e1, r1
